import java.util.Arrays;

/**
 * @Author YuanYuan
 * @Date 2022/5/9
 * @Time 8:48
 */
public class TestDemo {
    public static void myNext(int[] next,String arr) {
        int j = 2;
        int k = 0;
        next[0] = -1;
        next[1] = 0;
        while(j < arr.length()) {
                if(k == -1 || arr.charAt(j-1) == arr.charAt(k)) {
                    next[j] = k+1;
                    k++;
                    j++;
                }else {
                    k = next[k];
            }
        }
    }
    public static int myKMP(String arr1, String arr2,int pos) {
        if(arr1 == null||arr2 == null) {
            return -1;
        }
        if(arr1.length()==0||arr2.length()==0) {
            return -1;
        }
        if(pos<0||pos>=arr2.length()) {
            return -1;
        }
        int i = pos;
        int j = 0;
        int[] next = new int[arr2.length()];
        myNext(next,arr2);
        while(i< arr1.length()&& j < arr2.length()) {
            if(j == -1||arr1.charAt(i) == arr2.charAt(j)) {
                i++;
                j++;
            }else {
                //i++;
                j = next[j];
            }
        }
        if(j == arr2.length()) {
            return i-j;
        }
        return -1;
    }
    public static void main(String[] args) {
//        String arr1 = "001234124567";
//        String arr2 = "12341245";
//        String arr3 = "078";
        String arr4 = "abcababcabcd";
        String arr5 = "bcd";
        //System.out.println(myKMP(arr1,arr2));
        System.out.println(myKMP(arr4,arr5,0));
    }
}
